package offer;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * @Author SSK
 * @Date Created in 22:43 2019/8/8
 * @Description 滑动窗口的最大值
 * @Version 1.0
 */
public class T65 {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {    ArrayList<Integer> arrayList = new ArrayList<Integer>();
        if (num==null||size>num.length||size<=0) {
            return arrayList;
        }
        LinkedList<Integer> list = new LinkedList<Integer>();
        for (int i = 0; i < size; i++){
            if (list.size()==0) {
                list.add(i);
            }else if (num[i]<num[list.getLast()]){
                list.add(i);
            }else {
                while (!list.isEmpty()&&num[i]>=num[list.getLast()]) {
                    list.removeLast();
                }
                list.add(i);
            }
        }
        arrayList.add(num[list.getFirst()]);
        for (int i = size; i < num.length; i++) {
            if (num[i]<num[list.getLast()]){
                list.add(i);
            }else {
                while (!list.isEmpty()&&num[i]>=num[list.getLast()]) {
                    list.removeLast();
                }
                list.add(i);
            }
            if (i-list.getFirst()>=size) {
                list.removeFirst();
            }
            arrayList.add(num[list.getFirst()]);
        }
        return arrayList;
    }
}
